﻿// 1542. 找出最长的超赞子字符串.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>


using namespace std;
/*
https://leetcode.cn/problems/find-longest-awesome-substring/description/

给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。

「超赞子字符串」需满足满足下述两个条件：

该字符串是 s 的一个非空子字符串
进行任意次数的字符交换后，该字符串可以变成一个回文字符串


示例 1：

输入：s = "3242415"
输出：5
解释："24241" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "24142"

示例 2：
输入：s = "12345678"
输出：1

示例 3：
输入：s = "213123"
输出：6
解释："213123" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "231132"

示例 4：
输入：s = "00"
输出：2


提示：

1 <= s.length <= 10^5
s 仅由数字组成
*/

/*
01 记录每个状态值
遍历字符串  与当前状态相同 或者与当前状态仅有1个01位不同的最小索引即可成为超赞字符串。比对获取最长长度
*/

class Solution {
public:
    unordered_map<char, int> mm;
    void init() {
        for (int i = 0; i <= 9; i++) {
            mm['0' + i] = 1 << i;
        }
    }

    int longestAwesome(string s) {
        init();
        int mask = 0;
        unordered_map<int, int> prefix; prefix[0] = -1;
        int ans = 0;
        for (int i = 0; i < s.size(); i++) {
            mask ^= mm[s[i]];
            //cout << mask << endl;
            if (prefix.count(mask) == 0) { prefix[mask] = s.size() + 1; }
            ans = max(ans, i - prefix[mask]);
            prefix[mask] = min(i, prefix[mask]);
            //cout << "i = " << i << ". mask = " << mask << endl;
            for (int j = 0; j <= 9; j++) {
                int trymask = mask ^ (1 << j);
                if (trymask < 0) continue;
                if (prefix.count(trymask) == 0) { prefix[trymask] = s.size() + 1; }
                ans = max(ans, i - prefix[trymask]);
            }
            int dd = 9;
        }

        return ans;
    }
};




int main()
{
    Solution s;
    cout <<s.longestAwesome("11");
}

